#include <bits/stdc++.h>

using namespace std;

vector<string> letterCombinations(string digits);
void dfs(int idx, string digits);

int main()
{
	return 0;
}

array<string, 10> board = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
string layer;
vector<string> res;

vector<string> letterCombinations(string digits)
{
	if (digits.size() == 0) return res;
	dfs(0, digits);
	return res;
}

void dfs(int idx, string digits)
{
	if (idx == digits.size()) {
		res.emplace_back(layer);
		return;
	}

	string options = board[digits[idx] - '0'];
	for (const auto& ch : options) {
		layer.push_back(ch);
		dfs(idx + 1, digits);
		layer.pop_back();
	}
}
